AtCoder ABC 005 C - おいしいたこ焼きの売り方 (100点)

https://gyazo.com/2b95ec6803cfc6e4ecc727c42b0ff30e

https://gyazo.com/63eab768181b7d18f554d73d335bbe30

]

考察履歴

各パラメータの最大値が$ 100と小さいので$ O(N^2)のアルゴリズムでも間に合う

素朴にシミュレーションすれば良さそう

つまり、お客さんがきたら$ T秒以内に作られたたこ焼きがあるか判定し、

あればそのたこ焼きを売って、なければ売れないことが発生したことを記録する

たこ焼きを売るとは、たこ焼きリストから、そのたこ焼きを削除すること

たこ焼きの焼き上がり時間（入力$ A_i）で、各たこ焼きを区別する

一度でも売れなかったら、"no"を出力なので、boolで記録すれば良い。

ACコード

code:python

import sys

import math

sys.setrecursionlimit(10 ** 8)

ini = lambda: int(sys.stdin.readline())

inm = lambda: map(int, sys.stdin.readline().split())

inl = lambda: list(inm())

ins = lambda: sys.stdin.readline().rstrip()

debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

T = ini()

N = ini()

A = inl()

M = ini()

B = inl()

ans = "yes"

for p in B:

if len(tako) != 0:

A.remove(tako0)

else:

ans = "no"

print(ans)

最近(2020/9/10)の感じだとこれは灰diffレベルで、$ O(N)要求になってようやく茶diffくらいでは？

$ O(N)で実装する場合、

たこ焼きを確認していくインデックスを用意して、

最初の客で売れるたこ焼きがあったらそれを売って、そのたこ焼きのインデックスを保持

次の客は保持したインデックスからチェックを開始するようにする

これでたこ焼きリストAのチェックが１回ずつになる？